package 我的Java学习_算法基础.day_03;

public class _040_实战解题_哪个数字超过了一半 {
    public static void main(String[] args) {
        int[] a ={9,3,9,7,9,7,9,8,9};
        int key=solve(a);
        System.out.println(key);
    }
    private static int solve(int[] array){
        //候选数
        int candidate = array[0];
        //出现次数
        int nTimes = 1;
        //扫描数组
        for (int i = 1; i < array.length; i++) {
            //两两消减为0，应该把现在的元素作为候选数
            if(nTimes==0){
                candidate = array[i];
                nTimes = 1;
                continue;
            }
            //遇到和候选值相同的，次数加一
            if(candidate==array[i]){
                nTimes++;
            }else{
                nTimes--;
            }
        }
        return candidate;
    }
}
